package cn.hesion.dataStructures.sortingorder;

import cn.hesion.array.Array;

import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i]= (int) (Math.random()*80000);
        }
//        System.out.println("排序前");
//        System.out.println(Arrays.toString(arr));
        Long before = LocalDateTime.now().toInstant(ZoneOffset.of("+8")).toEpochMilli();
        System.out.println("排序前系统毫秒数:"+before);
//        selectSortTD(arr);
        radixSort(arr);
        Long after = LocalDateTime.now().toInstant(ZoneOffset.of("+8")).toEpochMilli();
        System.out.println("排序后系统时间毫秒数:"+after);
        System.out.println("本次选择排序共耗时:"+(after-before)+"ms");
    }
    public static void radixSortTD(int[] arr){

        //定义一个二维数组当桶，，每个桶就是一维数组

        int[][] bucket = new int[10][arr.length];

        //我们定义一个一维数组用来记录每个桶的数据的个数
        int[] bucketElement = new int[10];
        //第一轮排序（针对每个元素的个位数）
        for (int i = 0; i < arr.length; i++) {
            //从数组中取出这个数，算出他的个位数
            int digitOfElement = arr[i] % 10;
            bucket[digitOfElement][bucketElement[digitOfElement]]=arr[i];
            bucketElement[digitOfElement]++;
        }
        int index=0;
        //放入桶中的操作结束后，遍历桶，将桶中的元素依次取出放入原数组
        for (int i = 0; i < bucketElement.length; i++) {
            if(bucketElement[i] !=0){
                for (int j = 0; j < bucketElement[i]; j++) {
                      //取出元素，放入arr
                    arr[index++]=bucket[i][j];
                }
            }
            //为了下一步的继续进行，必须清零
            bucketElement[i]=0;
        }
        System.out.println("第一轮结果"+ Arrays.toString(arr));
        //第二轮排序（针对每个元素的个位数）
        for (int i = 0; i < arr.length; i++) {
            //从数组中取出这个数，算出他的十位数
            int digitOfElement = (arr[i] /10) % 10;
            bucket[digitOfElement][bucketElement[digitOfElement]]=arr[i];
            bucketElement[digitOfElement]++;
        }
        index=0;
        //放入桶中的操作结束后，遍历桶，将桶中的元素依次取出放入原数组
        for (int i = 0; i < bucketElement.length; i++) {
            if(bucketElement[i] !=0){
                for (int j = 0; j < bucketElement[i]; j++) {
                    //取出元素，放入arr
                    arr[index++]=bucket[i][j];
                }
            }
            //为了下一步的继续进行，必须清零
            bucketElement[i]=0;
        }
        System.out.println("第二轮结果"+ Arrays.toString(arr));
    }
    public static void radixSort(int[] arr){
        //定义一个二维数组当桶，，每个桶就是一维数组

        int[][] bucket = new int[10][arr.length];

        //我们定义一个一维数组用来记录每个桶的数据的个数
        int[] bucketElement = new int[10];
        int maxLenth=findTheMaxNumLenth(arr);
        //第n轮排序（针对每个元素的对位数,个，十百千位）
        //需要进行多少轮这样的操作，取决于最大那个数的位数
        for (int k = 0,n=1; k < maxLenth; k++,n*=10) {
            for (int i = 0; i < arr.length; i++) {
                //从数组中取出这个数，算出他的个位数
                int digitOfElement = (arr[i] / n) % 10;
                bucket[digitOfElement][bucketElement[digitOfElement]]=arr[i];
                bucketElement[digitOfElement]++;
            }
            int index=0;
            //放入桶中的操作结束后，遍历桶，将桶中的元素依次取出放入原数组
            for (int i = 0; i < bucketElement.length; i++) {
                if(bucketElement[i] !=0){
                    for (int j = 0; j < bucketElement[i]; j++) {
                        //取出元素，放入arr
                        arr[index++]=bucket[i][j];
                    }
                }
                //为了下一步的继续进行，必须清零
                bucketElement[i]=0;
            }
//            System.out.println("第"+(k+1)+"轮结果"+ Arrays.toString(arr));
        }

    }

    public static Integer  findTheMaxNumLenth(int[] arr){
        //假设第一个数为最大值
        int tempMax=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>tempMax){
                tempMax=arr[i];
            }
        }
        int length = (tempMax + "").length();
        return length;
    }
}
